1. Field of the Invention
The present invention relates to an improved technique for processing information using a computer network, and more particularly to an improved techniques for distributed processing with regard to constraint satisfaction problem and an improvement in technology for readily realizing flexible bonding of a plurality of the existing systems.
2. Description of the Related Art
Recently, a practical approach using the framework of a constraint satisfaction problem (CSP) has been made to various problems including production scheduling problems and facilities and parts layout problems. The constraint satisfaction problem refers to a problem of finding a combination of values satisfying a constraint for a plurality of variables.
In a constraint satisfaction problem, individual elements such as facilities or parts constituting an actual problem are represented by variables. In this case, there are many constraints that may include one requiring that the facilities and the parts be placed at least a predetermined distance apart between each two of them. These constraints are represented as constraints among variables. An actual thing, such as which one of several alternatives is to used or where in a plane or on a time-axis each element is to be placed, is represented by a specific value of each variable. After that, finding the values of the individual variables that satisfy the above-described constraint gives a solution of the problem.
That is, to find a solution is to find a combination of variable values that satisfy the constraint. A combination of such variable values represents, for instance, a working schedule or a semiconductor device layout. A part of a solution, for example, a combination of some of the variables, is called a partial solution. The processing of such a constraint satisfaction problem is based on the branch search that performs a search, for example, when there are several branches that are capable of acquiring several alternative variable values, with regard to what kind of alternatives exist as the next branches according to which one is selected from the current several branches.
Knowledge about problem solving, such as a processing procedure for solving a constraint satisfaction problem, is called problem solving knowledge. Knowledge about the elements, or variables, of a target, such as a schedule or a layout, to be solved as a constraint satisfaction problem and about a constraint among the elements or variables is called target knowledge.
One known solving method for this constraint satisfaction problem is a method in which a single problem solver provides knowledge about the problem and, at the same time, dissolves all the constraints. To xe2x80x9cdissolvexe2x80x9d a constraint is to assign specific values not conflicting with the constraint. FIG. 22 is a diagram showing the concept of a single problem solver which has both problem solving knowledge and target knowledge. The problem solver calls a method corresponding to individual target knowledge for problem solving.
However, for a large constraint satisfaction problem such as an actual scheduling problem, a target for which problem solving is performed is physically distributed and, in most cases, the decision making actions at several levels are performed concurrently. In addition, assigning all tasks to the single problem solver requires the unified management of a large amount of data and results in the disclosure of information associated with the local aspect of the problem at one particular point, thus making it difficult to ensure security.
In particular, it is difficult to apply the single, centralized system described above to an actual large problem. The constraint satisfaction problem is, for example, a power cut plan for work of electric power system facilities. The power cut plan for work of electric power system facilities sets up dates on which power transmission will be temporarily suspended to maintain, replace, or add various types of facilities (bus bar, power transmission line, power generator, transformer, etc.).
Most conventional systems for supporting the power cut plan for work of electric power system facilities collect the schedules of all stations in one location (Reference: xe2x80x9cDevelopment of Support System of Power Cut Plan for Workxe2x80x9d by Akitomo Otubo, Thoshio Takahasi, Datashi Saito, Kazue Simada, Masaya Ono, Hirotaka Nakano, Yosiaki Osako, pp.138-139, 1997 Power System Convention, 1997). However, the system according to the prior art such as described above must perform a huge amount of centralized calculation and therefore requires a long processing time because the scale is very large. In addition, when the result of centralized calculation is not accepted by stations, the centralized calculation must be repeated. This sometimes causes a communication bottleneck.
Another problem is that the centralization of processing or communication loads decreases the applicability to the dynamic environment in the real world. For this reason, a method for modeling an actual large constraint satisfaction problem and for solving the problem efficiently with a plurality of solvers in the distributed coordination mode is now being studied.
This problem solving method, which works in the distributed coordination mode through a plurality of problem solvers, allows individual stations in the electric power system to work together to solve constraints coordinatable locally among themselves, except when the constraints require system-wide information as in a current calculation. This method gives us many advantages; that is, it reduces the centralized calculation load, reduces the coordination time, and results in fewer modification requests from the schedule made by each station.
Recently, many actual problems are modeled as large constraint satisfaction problems. And, as the means for solving such modeled problems efficiently, more emphasis is placed now on the constraint satisfaction problem solving method which works in the distributed coordination mode described above.
The method for satisfying constraints in the distributed coordination mode is called a distributed constraint satisfaction or a distributed constraint satisfaction problem. The method sometimes uses a plurality of equal agents (problem solvers). Standard algorithms used for this method include the synchronous backtrack algorithm and the asynchronous backtrack algorithm (Reference: xe2x80x9cTutorial Distributed Search and Its Surroundingsxe2x80x9d by Makoto Yokoo, Computer Software Vol. 12, No. 1, pp. 31-86, January 1995/xe2x80x9cNew Development of CSP: Distributed/Dynamic/Incomplete CSPxe2x80x9d by Makoto Tokoo, Katsutosi Hirayama, Artificial Intelligence, Vol. 12, No. 3., pp. 381-389, May. 1997).
The synchronous backtrack algorithm executes the backtrack type search algorithm using a plurality of agents. In this algorithm, the order in which agents determine their variables is fixed. More specifically, the first agent temporarily determines the values of its own variables and sends the values (partial solution) to the next agent. The next agent determines the values of its own variables so that the values satisfy both the partial solution and the constraint and adds the values to the partal solution; it then sends the resulting partial solution to the next agent.
When some agent tries to determine the values of its own variables but finds that there is no value satisfying the partial solution and the constraint, the agent sends a value-change request (backtrack) message to the previous agent. In this synchronous backtrack algorithm, agents send the partial solution serially, allowing the knowledge owned by individual agents to be integrated and thereby giving a solution satisfying the constraints.
Sycara and his group proposed the back jumping algorithm developed by improving the search efficiency of the above-described backtrack algorithm. They are studying the application of that algorithm to the scheduling problem. (Reference: Sycara, K. P., Sadeh, N. and Fox, M. S., xe2x80x9cDistributed constrained heuristics searchxe2x80x9d, IEEE transactions on Systems, Man And Cybernetics, Vol. 21, No.6, pp. 1446-1461, 1991. Sycara, K. P., Roth, S. E, Sadeh, N. and Fox, M. S., xe2x80x9cResource Allocation in Distributed Factory Schedulingxe2x80x9d, IEEE Expert, Vol. 6, No. 1, pp. 29-40, 1991).
Unlike the backtrack algorithm described above, the asynchronous backtrack algorithm allows the agents to determine their own values asynchronously and concurrently based on the local information. And, the agents exchange the new constraint (nogood) with each other to find a combination of variable values satisfying the system-wide constraints.
The distributed constraint satisfaction technology like this include CORBA (Common Object Request Broker Architecture), an ORB (Object Request Broker) proposed by OMG (Object Management Group). The ORB is a mechanism responsible for execution, communication, and management of functionally-divided applications, each composed of objects, in a distributed system. This architecture not only provides the applications with the basic operation of the objects but also allows the applications to use sophisticated common and generic functions, such as printing and data exchange. It also provides business applications with the services common to all applications as well as the services specific to each application.
FIG. 23 is a diagram showing the concept of the architecture like CORBA described above. As shown in the figure, each object has both problem solving knowledge and target knowledge. To perform processing necessary for the target knowledge owned by an object, the object sends a message to some other object to use the method owned by that object.
Another distributed constraint satisfaction architecture is disclosed in Japanese Patent Laid-Open No. Hei 7-6157 and Japanese Patent Laid-Open No. Hei 9-91431. In this architecture, the agents resident in some nodes (called stationary agents) are used as schedulers each of which performs direct negotiation with other schedulers hereinafter called xe2x80x9cdirect negotiation modelxe2x80x9d).
FIG. 24 is a diagram showing how a plurality of stationary agents SA perform direct negotiation with each other. Note that, in the direct negotiation model, agents, not the objects, are used and that they are autonomous. Therefore, as shown in the conceptual diagram in FIG. 25, each agent autonomously decides which method to use according to the condition under which the agent processes its own target knowledge.
Another method of sharing knowledge is also known, such as a facilitator model implemented through DARPA knowledge sharing activity (The DARPA Knowledge Sharing Effort). In this model, a plurality of agents use the coordination facilitator to exchange knowledge via the common language for exchanging common knowledge (xe2x80x9cKnowledge Sharing and Reuse through Coordination Architecturexe2x80x9d by Toyoaki Nishida, Artificial Intelligence Society Magazine, Vol. 9, No. 1, January 1994, pp. 23-28). That is, in the facilitator model, the agents exchange knowledge via one facilitator.
However, the prior art of distributed constraint satisfaction described above has the following problems. First, for an ORB such as CORBA and the direct negotiation model described above, the communication functions such as the highly-sophisticated message routing function or communication protocol must be included in advance. This makes it difficult to develop a distributed scheduling system and to utilize the existing scheduling system.
In addition, including these communication functions into individual schedulers results in the already-included protocol being always used as the scheduler coordination protocol, making it difficult to add or change the protocol. Thus, it is difficult to efficiently implement or use the constraint satisfaction algorithm, best suited for the constraint type, for use as the coordination protocol. The coordination protocol, a protocol defining a sequence of information exchange actions among a plurality of subjects to achieve an object, may be represented, in general, as a state transition diagram.
In addition, including complex processing, such as scheduler communication or branch search, into the individual schedulers constituting the direct negotiation model results in the frequent data exchange among schedulers especially when the variables of the schedulers must be coordinated step by step. This increases both the processing load of the individual schedulers and the communication amount over the network connecting the schedulers.
When a branch search fails due to a network error and the search of a part is terminated abnormally in the ORB or the direct negotiation model described above, the whole processing is influenced.
In the facilitator model described above, communication processing centralization in one facilitator causes a system bottleneck. In addition, the facilitator performs only simple message routing but does not virtually perform coordination processing. That is, the facilitator is not responsible for the progress of the whole processing, nor does it tell the individual schedulers what to do next.
Another problem with the constraint satisfaction method in the above-described distributed coordination mode is that heuristics is not reflected on the solution. Heuristics, also called an exploratory method, is thought of as a rule-of-thumb equation in which solutions are discovered by evaluation of the progress made toward the final result.
It is pointed out that, in general, solution search efficiency depends largely on the heuristics factors such as a strategy for the decision of individual agent variables or the variable decision priority order among agents (Reference: xe2x80x9cConstraint Based Search and Its Applicationxe2x80x9d by Kazuo Miyashita, Artificial Intelligence Magazine, Vol. 12, No. 3, pp. 374-380, May 1997). For a constraint satisfaction problem having a plurality of solutions, heuristics has a strong impact on the quality of the final solution.
Typical heuristics includes the ability to switch the strategy or the priority described above depending upon the situation. However, since the strategy and the priority are determined by the system configuration according to the conventional algorithm for distributed constraint satisfaction, heuristics cannot be reflected well on the processing and, as a result, it is difficult to increase the quality of search efficiency and quality.
Consider the power cut plan for work of electric power system facilities described above as an example. The coordination among stations is not fixed but varies according to the period of the year (busy season and off-season), the relation among stations, or the processing power of maintenance companies. And, the selection and the weighting of objects depend dynamically on such changeable factors as the priority of schedule coordination, minimization of movement during the work period, averaging of work load, and reduction in the number of suspensions.
Thus, coordination should be made more flexible depending upon the situation by using the coordination method or strategy In addition, it is expected that Japanese electric power companies will have power generation departments and power transmission departments in the near future like European and American power companies and that medium and small-sized electric generation companies will enter the electric power industry. If such is the case, it is desirable that a flexible coordination method be used, instead of the conventional fixed coordination method, to satisfy the need from the requesting stations and requesting departments directly and easily.
However, the method according to the prior art uses a fixed strategy and priority. Even if the strategy may be changed, the whole processing must be re-executed each time the strategy is changed. Re-executing the whole processing for each strategy change requires a long time; in addition, it does not satisfy the need to find a solution more speedily.
Conventionally, even when there are a plurality of agents with equal priority, the method according to the prior art selects one of the agents sequentially. This method does not always give a solution satisfying individual agents and, therefore, there has been a need to increase the quality of a solution.
On the other hand, as computer networks have become popular rapidly, interconnection among applications over the network becomes more important. In particular, in conjunction with the setup of the network infrastructure and the trend toward the openness of application software, the need arises to interconnect applications via the network. (Reference: xe2x80x9cSoftware agentsxe2x80x9d by Genesereth, M. R. and Ketchpel, S. P., Special Issue on Intelligent Agents, Communications of the ACM, Vol. 37, No. 7, pp. 48-53, July. 1994/xe2x80x9cMobile Agent Technology Implementing Network Societyxe2x80x9d by Shiniti Motoida, Takashi Moriyasu, Takahiro Kawamura, Toshiba review, Vol. 53, No. 8, pp. 2-6, August 1998).
More specifically, it is desirable that the existing dedicated program, called the legacy system, and existing databases be used as much as possible and that, by working them together, efficient distributed systems be built and managed.
Representative applications include an experiment, called CALS (Commerce At Light Speed), which digitizes information relating to the whole life cycle of a product, EC (Electronic Commerce) such as online shopping, and inter-enterprise EC aiming at the electronic commerce among enterprises. To implement those applications, interconnection among applications over networks is a key to success.
Nowadays, a variety of technologies and standards are proposed to implement inter-system data exchange over networks. Some of the examples include SGML which is a document processing description system, XML which is a network version of SGML, and STEP which is used for representation and exchange of product technology data.
However, consistent operation of a distributed system requires knowledge sharing based on data exchange as well as the coordination among constituent elements that composes the distributed system. Lack of such a coordination function impairs the merit of the distributed system. However, in the conventional environment to develop such distributed system has never supported the coordination function sufficiently.
Recently, efforts have been made to develop a distributed object system using distributed system constituent elements as objects and a multi-agent system composed of a plurality of coordinating agents. However, most of development support tools for use on these systems have communication functions among constituent elements but not coordination functions among them. Therefore, a framework providing not only communication functions but also coordination functions is required. This framework is -a partially completed software product used to create specific parts for use in building an actual distributed system.
That is, recently, the distributed architecture is shifting from the conventional client-server model (FIG. 26) to the distributed object model (FIG. 27) which may be built more flexibly. This type of distributed object model generally requires that the connected systems understand each other-and that modeling and interface specifications be defined rigidly. For example, knowledge about the object (IDL interface and so on) of a remote partner must be known in advance. In addition, because the logic of coordination among a plurality of objects is not supported in the conventional object-oriented programming system, the object designer must include the logic into individual objects.
On the other hand, for the multi-agent model which is now under study, the constituent elements of a distributed system are regarded as agents. Several models are proposed for executing coordination among a plurality of agents.
Those models include KQML facilitators (Reference: xe2x80x9cActors: A model of Concurrent Computation in Distributed Systemsxe2x80x9d by Agha, G., The MIT Press, 1986/xe2x80x9cAn Overview of KQML: A knowledge Query and Manipulation Languagexe2x80x9d by Finin, T. and Wiederhold, G., Department of Computer Science, Stanford University, 1993./xe2x80x9cThe DARPA Knowledge Sharing Effort: Progress reportxe2x80x9d by Ybibitem{DARPA} Paaatil, P. S., Fikes, R. E., Patel-Schneider, P. E., Macay, D., Finin, T., Gruber, T. R. and Neches, R., Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, 1992.) and a model called a federation model.
However, creating the IP with the use of these tools is very complex. This is because each agent must have its own dedicated IP and that the IPs of all agents must be compatible. Therefore, when the user wants to add or modify some part of a problem solving procedure at initial time or during a production run, the complex interaction flow among agents must be broken down into the IP of each individual agent""s compatibly and repeatedly.
Agent development tools for the higher-level coordination function include COOL (Reference: xe2x80x9cCool: A language for describing coordination in multi agent systemsxe2x80x9d by Barbuceanu, M. and Fox, M. S., Proceedings of the First International Conference on Multi-Agent Systems, 1995.) and JAFMAS (Reference: xe2x80x9cJAFMAS: A JAVA-based Agent Framework for Multiagent Systems Development and Implementationxe2x80x9d by Chauhan, D., phD thesis, ECECS Department, University of Cincinnati, 1997).
These tools propose the general methodology for developing a multi-agent system based on Speech-Act (Reference: xe2x80x9cHow to do Things With Wordsxe2x80x9d by Austin, J. L.(ed), Oxford University Press, 1962). At the same time, the tools support an interaction protocol (hereinafter called IP) for explicitly representing inter-dependency among KQML messages. This IP, primarily composed of the communication element and the coordination element, is a procedure allowing constituent elements, such as applications, to communicate with each other and to coordinate the constituent elements to solve a given problem.
However, creating the IP with the use of these tools is very complex. This is because each agent must have its own dedicated IP and that the IPs of all agents must be compatible. Therefore, when the user wants to add or modify some part of a problem solving procedure at initial time or during a production run, the complex interaction flow among agents must be broken down into the IP of each individual agent compatibly and repeatedly.
In particular, this task is impractical when there are many related agents or when the problem solving procedure is very complex. At the same time, verifying whether or not the IPs of the agents are compatible becomes more difficult.
That is, the prior art attempted to achieve two objects at the same time: to process the difference in the interface formats which vary each constituent element just as dialects vary from district to district and to coordinate the interaction among individual constituent elements. This makes it difficult to develop the IP efficiently.
The present invention has been proposed in order to solving the problems of the related art described above. The first object of the present invention is to achieve in improved technique for distributed processing with regard to a constraint satisfaction problem. In other words, it is an object of the invention to cause an agent to mediate cooperation among a plurality of applications such as schedulers, thereby proceeding the whole processing smoothly, facilitating utilization of the existing applications and addition and change of cooperation protocols, avoiding concentration of processes and communications and reducing the range that is affected when a partial fault has occurred, and realizing flexible processing and improving search efficiency and quality of the solution.
The second object of the present invention is to provide a technique that can enhance flexible bonding of a plurality of the existing systems such as legacy systems and package software, by making use of a mediation agent.
The above-described problems in the prior art are solved by an improvement in information processing technology according to the present invention. In order to perform problem solving with regard to a given target, there are provided information processing systems and methods that mediate coordination among processing units by making use of at least one agent. In one aspect of the present invention, there is provided an information processing system comprising a plurality of processing units that form a distributed system and a means for generating at least one agent. Each processing unit has a first storage area storing target knowledge with regard to the target and problem solving knowledge representing how the problem solving is to be performed, and performs a part of the problem solacing by making use of the target knowledge and the problem solving knowledge. Each generated agent has a second storage area storing cooperation problem solving knowledge that represents how the plurality of units cooperate with each other to perform the problem solving, and mediates cooperation among the units by making use of the cooperation problem solving knowledge to cause each unit to perform the problem solving.
According to this information processing system, by causing the agent to mediate cooperation among the plurality of processing units, an exchange among processing units and management of the whole processing are realized, resulting in that it is unnecessary to give a high degree of autonomy such as a complicated cooperation protocol for each processing unit. Therefore, a plurality of processing units such as existing schedulers that are used individually, can be used as bases to be combined with each other, resulting in easy construction of systems such as distributed and cooperative type of scheduling systems.
Since a cooperation protocol is encapsulated in an agent, it is easy to add and change protocols. Concretely, it is supposed that constraint satisfaction algorithms and the like, which are most suitable to dissolve various type of constraints, are installed as cooperation protocols, and selectively used according to purposes and situations.
By building various cooperation protocols into each of the mobile agents respectively, and selectively using them according to situations, it is possible to dynamically add a new cooperation function to the individual schedulers. This means that it is possible to hide a cooperation protocol among schedulers, facilitating the use of a new protocol without restriction by an existing protocol.
Further, in this information processing system, desirably, each processing unit performs a process for problem solving and, when it is necessary to cooperate with another processing unit, generates an agent to execute a cooperation protocol among said processing units. In this case, since the application generates an agent as the need arises to allow a desired protocol to be used, an improvement in flexibility of operation is achieved.